package nowcoder.course;

import common.Util;

/**
 * @author fance
 * @date 18-6-11 下午12:37
 */
public class SortSum {
    void insertSort(int[] a,int n) {
        for (int i = 1; i < n; i++) {
            int tmp = a[i];
            int j = i;
            for (;j > 0 && a[j - 1] > tmp; j--) {
                a[j] = a[j - 1];
            }
            a[j] = tmp;
        }
    }

    void shellSort(int[] a, int n) {
        for (int increment = n / 2; increment > 0; increment /= 2) {
            for (int i = increment; i < n; i++) {
                int tmp = a[i];
                int j = i;
                for (; j >= increment; j -= increment) {
                    if (tmp < a[j - increment]) {
                        a[j] = a[j - increment];
                    } else {
                        break;
                    }
                }
                a[j] = tmp;
            }
        }
    }


    void selectSort(int[] a, int n) {
        for (int i = 0; i < n - 1; i++) {
            int small = i;
            for (int j = i + 1; j < n; j++) {
                if (a[j] < a[small]) {
                    small = j;
                }
            }
            if (small != i) {
                Util.swap(a,i,small);
            }
        }
    }

    void bubbleSortI(int[] a, int n) {
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n  - i; j++) {
                if (a[j] > a[j + 1]) {
                    Util.swap(a,j, j + 1);
                }
            }
        }
    }
    void bubbleSortII(int[] a, int n) {
        boolean flag = true;
        for (int i = 1; i < n && flag; i++) {
            flag = false;
            for (int j = 0; j < n  - i; j++) {
                if (a[j] > a[j + 1]) {
                    flag = true;
                    Util.swap(a,j, j + 1);
                }
            }
        }
    }

    static int[] tmp;
    void merge(int[] a, int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            tmp[k] = a[k];
        }
        for (int k = lo; k <= hi; k++) {
           if (i > mid) {
               a[k] = tmp[j++];
           } else if (j > hi) {
               a[k] = tmp[i++];
           } else if (tmp[i] < tmp[j]) {
               a[k] = tmp[i++];
           } else {
               a[k] = tmp[j++];
           }
        }

    }
        void mergeSort(int[] a, int n) {
            tmp = new int[n];
            mergeSort(a, 0, n - 1);
        }
        void mergeSort(int[] a,int lo, int hi) {
            if (hi <= lo) {
                return;
            }
            int mid = lo + (hi - lo) / 2;
            mergeSort(a,lo,mid);
            mergeSort(a,mid + 1,hi);
            merge(a,lo,mid,hi);
        }


    void quickSort(int[] a, int n) {
        quickSort(a, 0, n - 1);
    }
    void quickSort(int[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int j = partition(a, lo, hi);
        quickSort(a, lo, j - 1);
        quickSort(a, j + 1, hi);
    }
    public  int partition(int[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        int v = a[lo];
        while (true) {
            while (a[++i] < v) {
                if (i == hi) {
                    break;
                }
            }
            while (a[++j] > v) {
                if (j == lo) {
                    break;
                }
            }

            if (i >= j) {
                break;
            }

            Util.swap(a,i,j);
        }
        Util.swap(a,lo,j);
        return j;
    }


    int leftChild(int i) {
        return 2 * i + 1;
    }
    void sink(int[] a, int i, int n) {
        int child;
        int tmp = a[i];
        for (; leftChild(i) < n; i = child) {
            child = leftChild(i);
            if (child != n - 1 && a[child + 1] > a[child]) {
                child++;
            }

            if (tmp < a[child]) {
                a[i] = a[child];
            } else {
                break;
            }
        }
        a[i] = tmp;
    }

    void heapSort(int[] a, int n) {
        for (int i = n / 2; i >= 0; i--) {
            sink(a,i,n);
        }

        for (int i = n - 1; i > 0; i--) {
            Util.swap(a,0,i);
            sink(a,0,i);
        }
    }

    public int[] countingSort(int[] A, int n) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (A[i] > max) {
                max = A[i];
            }
        }
        int[] count = new int[max + 1];
        for (int i = 0; i < n; i++) {
            count[A[i]]++;
        }
        int index = 0;
        for (int i = 0; i < max + 1; i++) {
            while (count[i] != 0) {
                A[index++] = i;
                count[i]--;
            }
        }
        return A;
    }

    /**
     *  小范围排序练习题
     * @param A
     * @param n
     * @param k
     * @return
     */
    public int[] sortElement(int[] A, int n, int k) {
        for (int increment = k; increment > 0; increment--) {
            for (int i = increment; i < n; i++) {
                int tmp = A[i];
                int j = i;
                for (; j >= increment; j -= increment) {
                    if (tmp < A[j - increment]) {
                        A[j] = A[j - increment];
                    } else {
                        break;
                    }
                }
                A[j] = tmp;
            }
            
        }
        return A;
    }

    /**
     *重复值判断练习题
     * @param a
     * @param n
     * @return
     */
    public boolean checkDuplicate(int[] a, int n) {
        // write code here
        if (a == null || n < 1) {
            return false;
        }
        heapSort(a,n);
        for (int i = 0; i < n - 1; i++) {
            if (a[i] == a[i + 1]) {
                return true;
            }
        }
        return false;
    }

    /**
     * 有序数组合并练习题
     * @param A
     * @param B
     * @param n
     * @param m
     * @return
     */
    public int[] mergeAB(int[] A, int[] B, int n, int m) {
        int indexA = n - 1;
        int indexB = m - 1;
        int indexRes = n + m - 1;
        while (indexA >= 0 && indexB >= 0) {
            if (A[indexA] > B[indexB]) {
                A[indexRes--] = A[indexA--];
            } else {
                A[indexRes--] = B[indexB--];
            }
        }
        while (indexB >= 0) {
            A[indexRes--] = B[indexB--];
        }
        return A;
    }

    /**
     * 三色排序练习题
     * @param A
     * @param n
     * @return
     */
    public int[] sortThreeColor(int[] A, int n) {
        // write code here
        int first=0;
        int last=A.length-1;
        int cur=0;
        while(cur<=last){
            if (A[cur] == 0) {
                int temp = A[cur];
                A[cur]=A[first];
                A[first]=temp;
                first++;
            }
            if(A[cur]==2) {
                int temp = A[cur];
                A[cur] = A[last];
                A[last] = temp;
                last--;
                cur--;
            }
            cur++;
        }
        return A;
    }

    public boolean findX(int[][] mat, int n, int m, int x) {
        // write code here
        int i = 0;
        int j = m - 1;
        while (i < n && j >= 0) {
            if (mat[i][j] == x) {
                return true;
            } else if (mat[i][j] > x) {
                j--;
            } else {
                i++;
            }
        }
        return false;
    }

    public int shortestSubsequence(int[] A, int n) {
        int max = A[0];
        int min = A[n - 1];
        int r = 0;
        int l = 0;
        for (int i = 0; i < n; i++) {
            if (A[i] > max) {
                max = A[i];
            } else if (A[i] < max) {
                r = i;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            if (A[i] < min) {
                min = A[i];
            } else if (A[i] > min) {
                l = i;
            }
        }
        if (r == l) {
            return 0;
        } else {
            return r - l + 1;
        }
    }

    public int maxGap(int[] A, int n) {
        A = countingSort(A,n);
        int gap = 0;
        for (int i = 0; i < n - 1; i++) {
            gap = Math.max(gap,A[i + 1] - A[i]);
        }
        return gap;
    }
}
